package ink.lvxin.datastructure.ch2;

import ink.lvxin.datastructure.utils.NumberUtils;
/**
 * 最小序列和问题，4种算法
 * @author lx
 */
public class MaxSubSequence {
    public static void main(String[] args) {
        int[] arr = NumberUtils.getAbigArr(100000);
        long start = System.currentTimeMillis();
        long end;

        end = System.currentTimeMillis();
        System.out.println("max1 costs :" + (end - start) + " ms");
        start = end;
        System.out.println(maxSubSum2(arr));
        end = System.currentTimeMillis();
        System.out.println("max2 costs :" + (end - start) + " ms");
        start = end;
        System.out.println(maxSubSum3(arr,0,arr.length - 1));
        end = System.currentTimeMillis();
        System.out.println("max3 costs :" + (end - start) + " ms");
        start = end;
        System.out.println(maxSubSum4(arr));
        end = System.currentTimeMillis();
        System.out.println("max4 costs :" + (end - start) + " ms");
    }

    /**
     * O(N*N*N)
     * @param arr
     * @return
     */
    private static int maxSubSum1(int[] arr) {
        int maxSum = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                int subSum = 0;
                for (int k = i; k <= j; k++) {
                    subSum += arr[k];
                }

                if (subSum > maxSum) {
                    maxSum = subSum;
                }
            }
        }

        return maxSum;
    }

    /**
     * O(N*N)
     * @param arr
     * @return
     */
    private static int maxSubSum2(int[] arr) {
        int maxSum = 0;
        for (int i = 0; i < arr.length; i++) {
            int subSum = 0;
            for (int j = i; j < arr.length; j++) {
                subSum += arr[j];
                if (subSum > maxSum) {
                    maxSum = subSum;
                }
            }
        }

        return maxSum;
    }


    /**
     * O(NlogN)
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int maxSubSum3(int[] arr,int left,int right) {
        if (left == right) {
            return arr[left];
        }

        int mid = (right + left) / 2;
        int maxLeftArr = maxSubSum3(arr,left, mid);
        int maxRightArr = maxSubSum3(arr, mid + 1, right);

        int maxLeft = 0;
        int sumLeft = 0;
        for (int i = mid; i >= left; i--) {
            sumLeft += arr[i];
            if (sumLeft > maxLeft) {
                maxLeft = sumLeft;
            }
        }

        int maxRight = 0;
        int sumRight = 0;
        for (int i = mid + 1; i <= right; i++) {
            sumRight += arr[i];
            if (sumRight > maxRight) {
                maxRight = sumRight;
            }
        }

        int maxSum = maxLeft + maxRight;
        if (maxLeftArr > maxSum) {
            maxSum = maxLeftArr;
        }

        if (maxRightArr > maxSum) {
            maxSum = maxRightArr;
        }

        return maxSum;
    }

    /**
     * O(N)
     * perfect algorithm
     * on-line algorithm
     * @param arr
     * @return
     */
    private static int maxSubSum4(int[] arr) {
        int maxSum = 0;
        int thisSum = 0;
        for (int value : arr) {
            thisSum += value;
            if (thisSum > maxSum) {
                maxSum = thisSum;
            }
            if (thisSum < 0) {
                thisSum = 0;
            }

        }

        return maxSum;
    }


}
